package com.lw.leetcode.add.n;

/**
 * Created with IntelliJ IDEA.
 * b
 * binay
 * https://leetcode.cn/contest/cnunionpay2022/problems/6olJmJ/
 * 银联-2. 勘探补给
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/16 15:31
 */
public class ExplorationSupply {

    public int[] explorationSupply(int[] station, int[] pos) {
        int length = pos.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            int po = pos[i];
            int a = findMin(station, po - 1);
            int b = findMax(station, po + 1);
            arr[i] = Math.abs(po - station[a]) < Math.abs(po - station[b]) ? a : b;
        }
        return arr;
    }

    private int findMin(int[] station, int t) {
        int end = station.length - 1;
        if (station[end] <= t) {
            return end;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (station[m] > t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

    private int findMax(int[] station, int t) {
        if (station[0] >= t) {
            return 0;
        }
        int end = station.length - 1;
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (station[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

}
